package com.dy.排序和搜索.中级.探索二维矩阵2;

public class Solution {
    /**
     * 分治算法
     * 左下角的元素是这一行中最小的元素，同时又是这一列中最大的元素。比较左下角元素和目标：
     * 若左下角元素等于目标，则找到
     * 若左下角元素大于目标，则目标不可能存在于当前矩阵的最后一行，问题规模可以减小为在去掉最后一行的子矩阵中寻找目标
     * 若左下角元素小于目标，则目标不可能存在于当前矩阵的第一列，问题规模可以减小为在去掉第一列的子矩阵中寻找目标
     * 若最后矩阵减小为空，则说明不存在
     * ---------------------
     */
    public boolean searchMatrix(int[][] matrix, int target) {
        int row = matrix.length;

        if (row == 0) return false;
        int col = matrix[0].length;
        int i = row - 1, j = 0;
        while (i >= 0 && j < col) {
            if (matrix[i][j] == target) {
                return true;
            } else if (matrix[i][j] > target) {
                i--;
            } else {
                j++;
            }
        }
        return false;
    }

}
